package medium;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/4/4 13:59
 */
public class No79_单词搜索 {
    public static void main(String[] args) {
        Solution79 solution79 = new Solution79();
        char[][] board = new char[][]{
                {'s', 'f', 'c', 's'},
                {'a', 'd', 'e', 'e'},
                {'i', 'k', 'u', 'z'},
        };
        String word = "ikuzesce";
        boolean exist = solution79.exist(board, word);
        System.out.println(exist);
    }
}

class Solution79 {
    public boolean exist(char[][] board, String word) {
        //疯狂暴力,对每个格递归上下左右
        boolean res = false;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0)) {
                    res = exist(board, word, i, j, 0);
                    if (res) {
                        return res;
                    }
                }
            }
        }
        return res;
    }

    //wordIndex,word的wordIndex的字母char
    public boolean exist(char[][] board, String word, int x, int y,int wordIndex) {
        //全局最终结果,由word最后一个元素确定
        boolean res = false;
        //当前遍历元素的结果确定
        boolean curRes = false;
        if (x < 0 || y < 0 || x == board.length || y == board[0].length) {
            return res;
        }
        //word:FSU
        char word的对应位置的char = word.charAt(wordIndex);
        if (board[x][y] == word的对应位置的char) {
            curRes = true;
        }
        //只有全部匹配,res才变为true
        if (wordIndex == word.length() - 1 && curRes) {
            res = true;
            //为了让wordIndex不越界
            return res;
        }
        //能递归
        if (curRes && board[x][y] != '镖') {
            //做标记
            board[x][y] = '镖';
            //上 (||:为了将res 带回)
            res = res || exist(board, word, x - 1, y, wordIndex + 1) ||
            //下
            exist(board, word, x + 1, y, wordIndex + 1) ||
            //左
            exist(board, word, x, y - 1, wordIndex + 1) ||
            //右
            exist(board, word, x, y + 1, wordIndex + 1);
            //回溯,去掉标记
            board[x][y] = word的对应位置的char;
        }
        return res;
    }
    
    
}

